package com.syh.leecode.array;

import java.util.Arrays;

/**
 * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 */
public class MaximumProductThreeNumber {
    /**
     * 穷举
     * leecode 执行结果正确，提交提示超出时间限制
     * 时间复杂度 O(n^3)
     */
    public int maximumProductV1(int[] nums) {
        int result = nums[0]*nums[1]*nums[2];
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length;j++){
                for(int k=0;k<nums.length;k++){
                    if(i!=j&&j!=k&&k!=i){
                        int getResult = nums[i]*nums[j]*nums[k];
                        if(result<=getResult){
                            result = getResult;
                        }
                    }
                }
            }
        }
        return result;
    }
    /**
     * 第二次想到的是将nums 的数组下标做 排列组合，然后再每个统计最大值
     * 但是排列组合的时间复杂度应该还是O(n^3) 此方法pass
     * 再想就是把数组排序
     * 如果全为正数的话则，最大的三个数字相乘则是最大值
     * 如果有正有负 则最大值可能是最小的两位负数乘以最大的一位正数
     */
    public int maximumProductV2(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        return Math.max(nums[length-1]*nums[length-2]*nums[length-3],nums[0]*nums[1]*nums[length-1]);
    }

    /**
     * 根据V2的方法论我们注意到我们只要获取到最大的三个数 和最小的两个数五个数字即可
     * 根据v2改造过后的代码如下
     */
    public int maximumProductV3(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for(int x:nums){
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = x;
            }
            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }
        return Math.max(max1*max2*max3,min1*min2*max3);
    }
}
